package com.wangbo.heap;

/**
 * 大根堆
 */
public class BigRootHeap {
    public int[] heap;
    public int maxSize;
    public int heapSize;

    public BigRootHeap(int maxSize) {
        this.maxSize = maxSize;
        heap = new int[maxSize];
        heapSize = 0;
    }

    /**
     * 新增元素（大节点上浮）
     */
    public void add(int value) {
        if (isFull()) {
            throw new RuntimeException("堆已满");
        } else {
            heapInsert(value);
        }

    }

    /**
     * 堆调整(向上)
     * 新节点和父节点比较大小，较大则交换位置，直到新节点小于等于父节点
     */
    public void heapInsert(int value) {
        int index = heapSize++;
        int parent = (index - 1) / 2;  // 不用 >>, 因为负数需要向上取整
        heap[index] = value;
        // 大节点上浮
        while (heap[index] > heap[parent]) {
            swap(heap, parent, index);
            index = parent;
            parent = (index - 1) / 2;
        }
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 弹出根节点（小节点下沉）
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("堆已空");
        }

        int root = heap[0];
        swap(heap, 0, --heapSize); // 把最末元素移动到根节点位置
        heapify(heap, 0, heapSize); // 根节点下沉
        return root;
    }

    /**
     * 堆调整(向下)
     * index节点和左右孩子中的较大方比较大小，index节点较小则交换位置，继续向下比较，直到index节点大于等于或者没有孩子
     */
    public void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1; // 遍历指针，index 的左孩子下标
        while (left < heapSize) {
            int right = left + 1; // 遍历指针，index 的右孩子下标
            int bigger = right < heapSize && arr[right] > arr[left] ? right : left; // 左右子节点的较大方
            bigger = arr[bigger] > arr[index] ? bigger : index; // index和largest的较大方
            if (bigger == index) {
                break;
            } else {
                swap(arr, bigger, index);
                index = bigger;
                left = index * 2 + 1;
            }
        }
    }

    /**
     * 是否为空
     */
    public boolean isEmpty() {
        return heapSize == 0;
    }

    /**
     * 是否已满
     */
    public boolean isFull() {
        return heapSize == maxSize;
    }

}
